// ----------------------------------------------------------------------------
// sort_queue.h
// ----------------------------------------------------------------------------
/*
 Description:
 最小のデータを取り出す際にO(1)でデータを取得できるキュー構造.
 ※このコンテナはスレッドセーフではない.
 ※このコンテナはいわゆるプライオリティーキューではない.
 
 ----------------------------------------------------------------
 使い方.
 
 1. データ型と、比較用プレディケートオブジェクトを指定する.
 デフォルトでは、std::lessが利用されている. 
 
 typedef SortQueue<int> MinQueue_Int;
 
 2. データに任意のエレメントを追加していく. 
 Bestを呼び出すことで比較条件で最も優れたエレメントを取得できる.
 
 MinQueue_Int s;
 
 s.Enqueue(1);
 s.Enqueue(6);
 s.Enqueue(3);
 
 int value = s.Best();
 assert(value == 1);
 
 */
#pragma once
#include <fw/base/core/assertion.h>
#include <fw/base/container/sort_stack.h>
#include <functional>

namespace fw
{
    template < typename T, typename Comparator = std::less<T> > class SortQueue
    {
    private:
        mutable SortStack< T, Comparator >  m_new, m_old;
        Comparator                          m_comp;
        
        void                                MoveIfNecessary()
        {
            if(!m_old.Empty())
            {
                return;
            }
            // スタックを逆転する. 
            while(!m_new.Empty())
            {
                m_old.Push(m_new.Top());
                m_new.Pop();
            }
        }
        
    public:
        
        explicit SortQueue(Comparator c=Comparator())
        : m_new (c)
        , m_old (c)
        , m_comp(c)
        {
        }
        
        void                                Enqueue(const T& v)
        {
            m_new.Push(v);
        }
        
        void                                Dequeue()
        {
            MoveIfNecessary();
            m_old.Pop();
        }
        
        const T&                            Front() const
        {
            MoveIfNecessary(); // Dequeueした直後にFrontを実行される可能性がある. 
            return m_old.Top();
        }
        
        const T&                            Best()  const
        {
            if(!m_old.Empty() && !m_new.Empty())
            {
                return m_comp(m_old.Best(), m_new.Best()) ? m_old.Best() : m_new.Best();
            }
            else if(!m_old.Empty())
            {
                return m_old.Best();
            }
            else if(!m_new.Empty())
            {
                return m_new.Best();
            }
            FW_ASSERT(0, L"未定義の動作になります.\n");
            return m_new.Best();
        }
        
        size_t                              Size()  const
        {
            return m_new.Size() + m_old.Size();
        }
        
        bool                                Empty() const
        {
            return m_new.Empty() && m_old.Empty();
        }
        
        
    }; // class SortQueue 
    
} // namespace fw 
